package DP;

/**
 * https://leetcode-cn.com/problems/counting-bits/
 */
public class CountBits {

    /**
     * 这玩意的转移方程比较有意思
     * F[x] = F[x] % 2 + F[X >> 1]
     * 这里面%2的操作，其实 跟 &1的一样
     */
    public int[] countBits(int num) {
        int[] r = new int[num+1];
        r[0] = 0;
        for(int i=1; i<=num; i++){
            r[i] = (i & 1) + r[i >> 1];
        }

        return r;
    }



    public static void main(String[] args){
        int[] n = new int[]{-1,1,1,1};

    }


}
